import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class PathFinding {
//	static boolean[][] checked;
	// return true if there is a box in the position i,j
	public static boolean isABox (int i, int j, PlayerNBoxes pnb){
		boolean b=false;
		Position checkPos = new Position (i,j);
		for (int l=0; l<pnb.getBoxes().length;l++){
			if (checkPos.isEqual(pnb.getBoxes()[l])){
				b= true;
			}
		}
		return b;
	}
		
	//return the path between the player square and the square in argument if it's reachable, and "" if it's not
	public static String pathTo(Position goal, PlayerNBoxes p, Board b){

		Queue<Integer> qI= new LinkedList<Integer>();												//create queues for x and y values
		Queue<Integer> qJ= new LinkedList<Integer>();
		Queue<String>  qs= new LinkedList<String>();
		boolean[][] checked = new boolean[b.getNumRows()][b.getNumColumns()]; //all squares covered
		for(int i=0; i<b.getNumRows(); i++)
			for(int j=0; j<b.getNumColumns();j++)
				checked[i][j]=false;
		qI.add(p.getPlayer().getI());												//store the first point in the array
		qJ.add(p.getPlayer().getJ());
		qs.add("");

		int ti;	int tj;	String ts;
		while(!qI.isEmpty()){									//repeat until the queues are empty
			ti=qI.remove();	tj=qJ.remove();	ts=qs.remove();
			if( new Position(ti,tj).isEqual(goal) ) return ts;
			if( !checked[ti][tj] && b.getData(ti,tj) != Board.WALL && !isABox(ti,tj,p) ){ 	
				checked[ti][tj]=true;;		
				if(ti+1<b.getNumRows()) 	{	qI.add(ti+1); qJ.add(tj); qs.add(ts+"D ");}		//add all neighbors to the queue
				if(tj+1<b.getNumColumns())	{ 	qJ.add(tj+1); qI.add(ti); qs.add(ts+"R ");}			
				if(ti-1 >= 0) 				{ 	qI.add(ti-1); qJ.add(tj); qs.add(ts+"U ");}
				if(tj-1 >= 0) 				{ 	qJ.add(tj-1); qI.add(ti); qs.add(ts+"L ");}
			}
		}
		return "";
	}
	
	
	public static boolean isPathTo(Position p, PlayerNBoxes pnb, Board b){
		boolean bool = false;
		String st = pathTo(p, pnb, b);
		if (pnb.getPlayer().isEqual(p)) bool = true;
		if (st.length()!=0){
			bool = true;
		}
		return bool;
	}
	
	
	public static String finalPath2(ArrayList<Move> moves, Board initialBoard, PlayerNBoxes initialPnb){
		
		String solution = "";
		String oneWay = "";
//		Board acutalBoard = new Board(initialBoard);		
		PlayerNBoxes actualPnb = new PlayerNBoxes(initialPnb);
//		Move [] m = (Move[]) moves.toArray();
		
//		ArrayList<Move> allMoves = new ArrayList<Move>();
//		for (int i = 0; i < m.length; i++){
//			allMoves.add(m[i]);
//		}
		
		
		for (int j = 0; j<moves.size(); j++){
			//Find the target square
			Position target;
			Position targetBox = new Position(moves.get(j).getStart());//the position of the box before moving
			if (moves.get(j).getDirection() == Move.MOVE_UP)
				target = new Position(targetBox.getI()+1,targetBox.getJ());
			else if (moves.get(j).getDirection() == Move.MOVE_DOWN)
				target = new Position(targetBox.getI()-1,targetBox.getJ());
			else if (moves.get(j).getDirection() == Move.MOVE_LEFT)
				target = new Position(targetBox.getI(),targetBox.getJ()+1);
			else
				target = new Position(targetBox.getI(),targetBox.getJ()-1);
			
			//find the way of the player
	//		System.out.print("move from " + actualPnb.getPlayer().toString() + "to " + target.toString() + " ");
			oneWay = PathFinding.pathTo(target, actualPnb, initialBoard);
	//		System.out.println(oneWay);
			//add the last movement
			if (moves.get(j).getDirection() == Move.MOVE_UP)
				solution += oneWay+"U ";
			else if (moves.get(j).getDirection() == Move.MOVE_DOWN)
				solution += oneWay+"D ";
			else if (moves.get(j).getDirection() == Move.MOVE_LEFT)
				solution += oneWay+"L ";
			else
				solution += oneWay+"R ";
			
			//update the player&boxes
			actualPnb.moveBox(moves.get(j).getStart(), moves.get(j).getEnd());
			
			actualPnb.setPlayer(moves.get(j).getStart());
		}
		
		return solution;
	}
	
}



























//import java.util.ArrayList;
//import java.util.HashSet;
//
//
//public class PathFinding {
//
//	
//	// return true if there is a box in the position i,j
//	private static boolean isABox (int i, int j, PlayerNBoxes pnb){
//		boolean b=false;
//		Position checkPos = new Position (i,j);
//		for (int l=0; l<pnb.getBoxes().length;l++){
//			if (checkPos.isEqual(pnb.getBoxes()[l])){
//				b= true;
//			}
//		}
//		return b;
//	}
//	
//	
//	
//	
//	
//	
//	//return the path between the player square and the square in argument if it's reachable, and "" if it's not
//	public static String pathTo(Position goal, PlayerNBoxes p, Board b){	
//		String s = ""; //the string to return 
//		Position actualPlayer = new Position(p.getPlayer());  //player's square initialized at getPlayer
//		ArrayList<Position> lLastSquares = new ArrayList<Position>(); //all squares covered
////		ArrayList<int[]> lMovesPlayer = new ArrayList<int[]>(); //
//		
//		int it = 0; //count the number of iteration
//		
//		while (!actualPlayer.isEqual(goal) && it<50){
//			lLastSquares.add(new Position(actualPlayer)); // add the initial position to the visited position
//			int smallerDistance = 10000;
//			int effectivMov = -1; //the best move
//			if (b.getData(actualPlayer.getI()-1, actualPlayer.getJ())!=Board.WALL && !isABox(actualPlayer.getI()-1, actualPlayer.getJ(),p) ){
//				int x = goal.getI()-(actualPlayer.getI()-1);
//				int y = goal.getJ()-actualPlayer.getJ();
//				int dist = x*x+y*y;
//				Position ip= new Position(actualPlayer.getI()-1, actualPlayer.getJ());
//				int ind = 0;
//				for (int f=0;f<lLastSquares.size();f++){
//					if (ip.isEqual(lLastSquares.get(f))){
//						ind = f+1;
//					}
//				}
//				dist += ind*10; //number added if the square has already been visited
//				if (dist<smallerDistance){
//					smallerDistance = dist;
//					effectivMov = 0;
//				}
//			} 
//			if  (b.getData(actualPlayer.getI()+1, actualPlayer.getJ())!=Board.WALL && !isABox(actualPlayer.getI()+1,actualPlayer.getJ(),p) ){
//				int x = goal.getI()-(actualPlayer.getI()+1);
//				int y = goal.getJ()-actualPlayer.getJ();
//				int dist = x*x+y*y;
//				Position ip= new Position(actualPlayer.getI()+1, actualPlayer.getJ());
//				int ind = 0;
//				for (int f=0;f<lLastSquares.size();f++){
//					if (ip.isEqual(lLastSquares.get(f))){
//						ind = f+1;
//					}
//				}
//				dist += ind*10;				if (dist<smallerDistance){
//					smallerDistance = dist;
//					effectivMov = 1;
//				}
//			} 
//			if (b.getData(actualPlayer.getI(), actualPlayer.getJ()-1)!=Board.WALL && !isABox(actualPlayer.getI(),actualPlayer.getJ()-1,p) ){
//				int x = goal.getI()-actualPlayer.getI();
//				int y = goal.getJ()-(actualPlayer.getJ()-1);
//				int dist = x*x+y*y;
//				Position ip= new Position(actualPlayer.getI(), actualPlayer.getJ()-1);
//				int ind = 0;
//				for (int f=0;f<lLastSquares.size();f++){
//					if (ip.isEqual(lLastSquares.get(f))){
//						ind = f+1;
//					}
//				}
//				dist += ind*10;
//				if (dist<smallerDistance){
//					smallerDistance = dist;
//					effectivMov = 2;
//				}
//			}
//			if (b.getData(actualPlayer.getI(), actualPlayer.getJ()+1)!=Board.WALL && !isABox(actualPlayer.getI(), actualPlayer.getJ()+1,p) ){
//				int x = goal.getI()-actualPlayer.getI();
//				int y = goal.getJ()-(actualPlayer.getJ()+1);
//				int dist = x*x+y*y;
//				Position ip= new Position(actualPlayer.getI(), actualPlayer.getJ()+1);
//				int ind = 0;
//				for (int f=0;f<lLastSquares.size();f++){
//					if (ip.isEqual(lLastSquares.get(f))){
//						ind = f+1;
//					}
//				}
//				dist += ind*10;				if (dist<smallerDistance){
//					smallerDistance = dist;
//					effectivMov = 3;
//				}
//			} 
//			
//			
//			
//			
//			if (effectivMov == 0){
//				actualPlayer.setI(actualPlayer.getI()-1);
//				s += "U ";				
//			}
//
//			if (effectivMov == 1){
//				actualPlayer.setI(actualPlayer.getI()+1);
//				s += "D ";				
//			}
//		
//
//			if (effectivMov == 2){
//				actualPlayer.setJ(actualPlayer.getJ()-1);
//				s += "L ";				
//			}
//
//			if (effectivMov == 3){
//				actualPlayer.setJ(actualPlayer.getJ()+1);
//				s += "R ";				
//			}
//			
//			it++;
////			System.out.println(s);
//			
////			lLastSquares.add(new Position (actualPlayer.getX(), actualPlayer.getY()));
//			
//		}//end of while
//		if (it>=50){
//			s = "";
//		}
//		//System.out.println("path before simplification" + s);
//		
//
//		String stri = simplifyPath(simplifyPath(s));
//		return stri;
//	}// end of function
//	
//	
//	
//	public static boolean isPathTo(Position p, PlayerNBoxes pnb, Board b){
//		boolean bool = false;
//		String st = pathTo(p, pnb, b);
//		if (pnb.getPlayer().isEqual(p)) bool = true;
//		if (st.length()!=0){
//			bool = true;
//		}
//		return bool;
//	}
//	
//	
//	private static String simplifyPath(String s){
//		String t1, t2, t3, t4;
//		t1 = s.replace("U D ", "");
//		t2= t1.replace("D U ", "");
//		t3= t2.replace("R L ", "");
//		t4 =t3.replace("L R ", "");
//		
//		return t4;
//		
//	}
//	
//	
//	
////	public static String finalPath(ArrayList<Node> nodes, Board initialBoard, PlayerNBoxes initialPnb){
////		
////		String solution = "";
////		String oneWay = "";
//////		Board acutalBoard = new Board(initialBoard);		
////		PlayerNBoxes actualPnb = new PlayerNBoxes(initialPnb);
//////		Move [] m = (Move[]) moves.toArray();
////		
//////		ArrayList<Move> allMoves = new ArrayList<Move>();
//////		for (int i = 0; i < m.length; i++){
//////			allMoves.add(m[i]);
//////		}
////		
////		
////		for (int j = 0; j<nodes.size(); j++){
////			//Find the target square
////			Position target;
////			Position targetBox = new Position(nodes.get(j).getPrevMove().getStart());//the position of the box before moving
////			if (nodes.get(j).getPrevMove().getDirection() == Move.MOVE_UP)
////				target = new Position(targetBox.getI()+1,targetBox.getJ());
////			else if (nodes.get(j).getPrevMove().getDirection() == Move.MOVE_DOWN)
////				target = new Position(targetBox.getI()-1,targetBox.getJ());
////			else if (nodes.get(j).getPrevMove().getDirection() == Move.MOVE_LEFT)
////				target = new Position(targetBox.getI(),targetBox.getJ()+1);
////			else
////				target = new Position(targetBox.getI(),targetBox.getJ()-1);
////			
////			//find the way of the player
////			oneWay = PathFinding.pathTo(target, actualPnb, initialBoard);
////		
////			//add the last movement
////			if (nodes.get(j).getPrevMove().getDirection() == Move.MOVE_UP)
////				solution += oneWay+"U ";
////			else if (nodes.get(j).getPrevMove().getDirection() == Move.MOVE_DOWN)
////				solution += oneWay+"D ";
////			else if (nodes.get(j).getPrevMove().getDirection() == Move.MOVE_LEFT)
////				solution += oneWay+"L ";
////			else
////				solution += oneWay+"R ";
////			
////			//update the player&boxes
////			actualPnb.moveBox(nodes.get(j).getPrevMove().getStart(), nodes.get(j).getPrevMove().getEnd());
////			
////			actualPnb.setPlayer(nodes.get(j).getPrevMove().getStart());
////		}
////	
////		return solution;
////	}
// 	
//	
//	
//	public static String finalPath2(ArrayList<Move> moves, Board initialBoard, PlayerNBoxes initialPnb){
//		
//		String solution = "";
//		String oneWay = "";
////		Board acutalBoard = new Board(initialBoard);		
//		PlayerNBoxes actualPnb = new PlayerNBoxes(initialPnb);
////		Move [] m = (Move[]) moves.toArray();
//		
////		ArrayList<Move> allMoves = new ArrayList<Move>();
////		for (int i = 0; i < m.length; i++){
////			allMoves.add(m[i]);
////		}
//		
//		
//	for (int j = 0; j<moves.size(); j++){
//		//Find the target square
//		Position target;
//		Position targetBox = new Position(moves.get(j).getStart());//the position of the box before moving
//		if (moves.get(j).getDirection() == Move.MOVE_UP)
//			target = new Position(targetBox.getI()+1,targetBox.getJ());
//		else if (moves.get(j).getDirection() == Move.MOVE_DOWN)
//			target = new Position(targetBox.getI()-1,targetBox.getJ());
//		else if (moves.get(j).getDirection() == Move.MOVE_LEFT)
//			target = new Position(targetBox.getI(),targetBox.getJ()+1);
//		else
//			target = new Position(targetBox.getI(),targetBox.getJ()-1);
//		
//		//find the way of the player
////		System.out.print("move from " + actualPnb.getPlayer().toString() + "to " + target.toString() + " ");
//		oneWay = PathFinding.pathTo(target, actualPnb, initialBoard);
////		System.out.println(oneWay);
//		//add the last movement
//		if (moves.get(j).getDirection() == Move.MOVE_UP)
//			solution += oneWay+"U ";
//		else if (moves.get(j).getDirection() == Move.MOVE_DOWN)
//			solution += oneWay+"D ";
//		else if (moves.get(j).getDirection() == Move.MOVE_LEFT)
//			solution += oneWay+"L ";
//		else
//			solution += oneWay+"R ";
//		
//		//update the player&boxes
//		actualPnb.moveBox(moves.get(j).getStart(), moves.get(j).getEnd());
//		
//		actualPnb.setPlayer(moves.get(j).getStart());
//	}
//	
//	return solution;
//}
//	
//	
//	
//	
//}
//
//

